/*
 * @lc app=leetcode.cn id=87 lang=cpp
 *
 * [87] 扰乱字符串
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    map<pair<string, string>, bool> res;

    bool isScramble(string s1, string s2)
    {
        {
            pair<string, string> p(s1, s2);
            if (res.find(p) != res.end())
            {
                return res[p];
            }
        }

        bool ret_flag = false;

        if (s1.length() != s2.length())
            ret_flag = false;
        else if (s1.length() <= 1)
            ret_flag = s1 == s2;
        else if (s1 == s2)
            ret_flag = true;
        else
        {
            map<char, int> m1, m2;
            for (int i = 0; i < s1.length(); i++)
            {
                m1[s1[i]]++;
                m2[s2[i]]++;
            }

            bool flag = true;

            for (auto &it : m1)
            {
                if (it.second != m2[it.first])
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                ret_flag = false;
            }
            else
            {
                flag = false;
                for (int i = 1; i < s1.length() && !flag; i++)
                {
                    flag = isScramble(s1.substr(0, i), s2.substr(0, i)) &&
                           isScramble(s1.substr(i, s1.length() - i), s2.substr(i, s2.length() - i));

                    if (!flag)
                        flag = isScramble(s1.substr(0, i), s2.substr(s2.length() - i, i)) &&
                               isScramble(s1.substr(i, s1.length() - i), s2.substr(0, s2.length() - i));
                }
                ret_flag = flag;
            }
        }

        {
            pair<string, string> p(s1, s2);
            res[p] = ret_flag;
        }
        return ret_flag;
    }
};
// @lc code=end
